package nachos.vm;

import java.util.LinkedList;

import nachos.machine.Lib;

/* 
 * 数据结构:
 * 一个空闲位置的数组
 * 一个数组，下标为index，内容为counter，最小的即为最优置换位置
 * 提供接口：
 * in : 获知某位置被使用的消息
 * out: 返回空闲位置或-1
 * out: 返回最优置换位置
 */
/**
 * This class is the implement of core algorithm of managing the limited resources.
 * It implements the aging algorithm of NRU(LRU's simulation). 
 * Is used in page table and TLB.
 * 
 * @author sylvia
 *
 */
public class FreePositionManager {
	/**
	 * Establish a new FreePositionManager
	 * 
	 * @param num number of the position altogether
	 * 
	 */
	public FreePositionManager(int num){
		Lib.debug(VMProcess.dbgVM, "total num = " + num);
		totalNum = num;
		counters = new int[num];
		freePositionList = new LinkedList<Integer>();
		for (int i = 0; i < num; i ++){
			counters[i] = 0x00;
			freePositionList.add(i);
		}
		posLocked = new boolean[num];
	}
	
	/**
	 * Inform me while used
	 * @param index
	 */
	public void informUsePosition(int index){
		if (freePositionList.contains(index)){
			freePositionList.remove((Integer)index);
		}
		
		for (int i = 0; i < totalNum; i ++){
			counters[i] /= 2;
		}
		counters[index] = counters[index] | 0x80;
		//Lib.debug(VMProcess.dbgVM, "use page : ppn = " + index);
	}
	
	/**
	 * Return the best position to be placed
	 * @return
	 */
	public int getBestPosition(){
	int minIndex;
		minIndex = 0;
		for (int i = 0; i < totalNum; i++){
			if (posLocked[i])
				continue;
			if (counters[i] < counters[minIndex])
				minIndex = i;
		}		
		Lib.assertTrue(!(minIndex == 0 && posLocked[minIndex]));
		return minIndex;
	}
	
	/**
	 * Return a free position
	 * @return a free position, or -1 if doesn't exist
	 */
	public int getFreePosition(){
		if (freePositionList.isEmpty()){
			return -1;
		}
		else{
			return freePositionList.remove();
		}
	}
	
	public void setFreePosition(int pos){
		freePositionList.add(pos);
	}
	
	public boolean hasFreePosition(){
		return (!freePositionList.isEmpty());
	}
	
	public void printFreePos(){
		Lib.debug(VMProcess.dbgVM, "\tfreePosition : ");
		for (Object index : freePositionList.toArray()){
			Lib.debug(VMProcess.dbgVM, "\t\t" + (Integer) index);
		}
	}
	
	public void printCounters(){
		Lib.debug(VMProcess.dbgVM, "\tcounters : ");
		for (int c : counters){
			Lib.debug(VMProcess.dbgVM, "\t\t" + c);
		}
	}
	
	public void lockPos(int i){
		Lib.assertTrue(i >= 0 && i < totalNum);
		posLocked[i] = true;
		return;
	}
	
	public void unlockPos(int i){
		Lib.assertTrue(i >= 0 && i < totalNum);
		posLocked[i] = false;
		return;
	}
	
	/** total number of the positions */
	int totalNum;
	
	/** free position list */
	LinkedList<Integer> freePositionList;
	
	/** page locked */
	private boolean[] posLocked;
	
	/** counters for occupied positions */
	int []counters;
	
	
}
